package code.c03_stackQueue.sqStack;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/2 20:41
 * @package code.c03_stackQueue.SqStack
 * @description 【例3.6】
 * 有1～n的n个元素，通过一个栈可以产生多种出栈序列，
 * 设计一个算法判断序列b是否得为一个合适的出栈序列，并给出操作过程。要求用相关数据进行测试。
 */

public class Exam_3_6_2 {
    static String op = "";
    static int cnt;

    public static boolean isSerial(int[] b) {
        int i, j, n = b.length;
        Integer e;
        int[] a = new int[n];
        SqStackClass<Integer> st = new SqStackClass<>();
        // 将 1~n 放入到数组中
        for (i = 0; i < n; i++) {
            a[i] = i + 1;
        }
        i = 0;
        j = 0;
        while (i < n) {
            st.push(a[i]);
            op += " 元素" + a[i] + "进栈\n";
            i++;
            while (!st.empty() && st.peek() == b[j]) {
                e = st.pop();
                op += " 元素" + e + "出栈\n";
                j++;
            }
        }
        return st.empty();
    }

    /**
     * 求解算法
     *
     * @param b
     */
    public void solve(int[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i] + " ");
        }
        if (isSerial(b)) {
            System.out.println("是合法的出栈序列");
            System.out.println(op);
        } else {
            System.out.println("不是合法的出栈序列");
        }
    }

    public static void main(String[] args) {
        Exam_3_6_2 exam_3_6 = new Exam_3_6_2();
        System.out.println("测试1");
        int[] b1 = {1, 3, 2, 4};
        exam_3_6.solve(b1);

        System.out.println("测试2");
        int[] b2 = {4, 3, 1, 2};
        exam_3_6.solve(b2);
    }
}
